package basealgorithm;

import org.junit.Test;

/**
 * @author : sicaolong
 * @description :
 * @date : 2021/2/17  12:15 上午
 */
public class 第k小的数 {
    public int quickSort(int[] nums, int left, int right, int k) {
        if (left == right) return nums[left];
        int i = left - 1;
        int j = right + 1;
        int x = nums[left];
        while (i < j) {
            while (nums[++i] < x) ;
            while (nums[--j] > x) ;
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        int leftNum = j - left + 1;
        if (leftNum >= k) return quickSort(nums, left, j, k);
        return quickSort(nums, j + 1, right, k - leftNum);
    }

    @Test
    public void test() {
        int[] nums = new int[]{3, 2, 5, 4, 1};
        System.out.println(quickSort(nums, 0, 4, 4));
    }
}